KokaでAlgebraic Effectsに触れる

Algebraic Effectsをざっくり言うと、

プログラムの副作用をEffectとして表現し、

Effectの発生箇所と処理箇所を分離するような抽象化の手法

Effect TypesとEffect Handlersを用いてEffectを制御する

関数型言語だが、気持ち的にはあまりビビることなく手続き型っぽく書ける

転がっている文書を読むのも良いが、実際に動くものに触れるのが一番早い

疑似Haskellとか疑似JavaScriptのコードを読む必要はない

最初からそのためにデザインされた言語に触れたほうがノイズが少ない

あと、基本的なことを抑えるだけならKokaってかなり難易度低いと思う

覚えることが少ない

docsに「Minimal but General」と書かれてるけど本当にそのとおり

使いこなせるかどうかはさておき、「Algebraic Effectsを知りたい」だけならコスパが良い

Kokaの基本文法を抑えた後に、具体例をいくつか見ればイメージを掴める

KokaはAlgebraic Effects以外にもすごい点がいくつかあって面白いが、ここでは触れない

以下ではKoka v2.4.0を使っている

まずTypeScriptで例外をthrowする関数を書いてみる

code:ts

function safeDivide(a: number, b: number): number {

if (b === 0) {

throw new Error("Division by zero");

}

return a / b;

}

これは例外が発生しうる関数だが、そのことが関数の型に表れない

そのため、関数の使用者は内部を把握しないと、その仕様の存在に気づけない

また、例外が送出された場合、どこかでそれを捕捉する必要があるが、気付けない場合はそもそも捕捉のしようがない

更に、一度、例外がthrowされると、この関数の実行は中断されてしまう

そのため、例外が発生した地点から処理を再開することができない

次にHaskellを用いた除算関数を見る

code:hs

safeDivide :: Float -> Float -> Either String Float

safeDivide a b =

if b == 0 then

Left "Division by zero"

else

Right (a / b)

型があることで、失敗時のhandlingを強制することができる

しかし、Eitherという文脈が値に付くことで、通常の値との互換性がなくなってしまった

計算する場合は、値を取り出したり何なりする必要がある

更に、複数のモナドを組み合わせる時はモナド変換子を使うことが多いが、これもまた複雑になりがち

code:hs

import Control.Monad.Writer (MonadWriter, WriterT, tell, runWriterT)

import Control.Monad.Trans.Class (lift)

safeDivide :: (Monad m, MonadWriter Log m) => Float -> Float -> m (Either String Float)

safeDivide a b = do

if b == 0 then do

return $ Left "Division by zero"

else do

return $ Right (a / b)

main :: IO ()

main = do

(result, log) <- runWriterT (safeDivide 1 0)

putStrLn $ "Result: " ++ show result

putStrLn $ "Log: " ++ show log

これはWriterとEitherを組み合わせた例

モナドをネストさせたモナドスタックを構成することになるが、

順序を入れ替えたいときに型の構成をごちゃごちゃ入れ替えないといけなかったり、

組み合わせ自体が面倒だったりする

ここで、Kokaで除算関数を書くと以下のようになる

code:koka(js)

// raiseというEffectの定義

effect raise

ctl raise(msg: string): int

// 除算する関数の定義

fun safe-divide(x: int, y: int): raise int

if y==0 then raise("div-by-zero") else x / y

以下のようにして使う

code:koka(js)

fun raise-const(): int

with handler

ctl raise(msg) 42

8 + safe-divide(1,0)

code:result

42

以下で1箇所ずつ順に見ていく

Kokaの関数の型を見る

fun safe-divide(x: int, y: int): raise int

これを「Effect Type」と呼んだりする

そのため、省略しても良い

Effect Typeはbuilt-inで用意されているものもあれば、自分で定義することもできる

total

Effectが存在しないことを表す

exn

例外が発生する可能性がある

div

関数が終了しない可能性がある

console

consoleに書き込む可能性がある

etc.

また、これらの複数の組み合わせに対してaliasをつけることもできる

pure = <exn,div>

純粋関数であることを表す

io = <exn,div,ndet,console,net,fsys,ui,st<global>>

etc.

具体的な関数の型を見てみてもわかりやすいかも

code:koka(js)

effect raise // ①

ctl raise(msg: string): a // ②

これらは異なる名前でも良いし、複数のoperationを持っても良い

このeffectを使った関数を定義

code:koka(js)

fun safe-divide(x: int, y: int): raise int

if y==0 then raise("div-by-zero") else x / y

型シグネチャに表れている方がeffect type(①)で、

関数内に書かれているのがoperaion(②)ということ

interfaceのみ示されており、実装はまだ決まっていないということ

Effect Handlerとともに使用する

Effect Handlerは、内部でEffectが呼ばれたときに、どういう挙動をするかを定義する場所

内部で用意されたInterfaceに、実装をInjectionするイメージ

code:koka(js)

fun raise-const(): int

with handler // ③

ctl raise(msg) 42

8 + safe-divide(1,0) // ④

③でhandlingの仕方を定義した上で、④で実際に関数を呼んでいる

TypeScriptのtry/catchを順序を逆にして書いてると捉えれば良い

code:ts

try {

return safeDivide(1, 0); // ④に相当

} catch (msg: any) { // ③に相当

return 42

}

Handleされた時点から処理を再開することもできる

例えば上記のコードを以下のように書き換える

code:koka(js)

fun raise-const()

with ctl raise(msg) resume(42) // resumeしながら42

8 + safe-divide(1,0)

また、複数のEffectを扱う関数も簡単に書ける

code:koka(js)

effect ctl raise(msg: string): a

effect ctl log(msg: string): ()

fun safe-divide(x: int, y: int): <log,raise> int

if y==0

then

log("Division by zero attempted")

raise("div-by-zero")

else

log("Performing division")

x / y

fun raise-const(): console int

with ctl raise(msg) 42 // ①

with fun log(msg) // ②

println(msg)

8 + safe-divide(1,0)

更に、handleする順序の入れ替えも、行を入れ替えるだけで良いのでかなり楽

code:koka(js)

fun raise-const(): console int

with ctl raise(msg) 42

with fun log(msg)

println(msg)

...

code:koka(js)

fun raise-const(): console int

with fun log(msg)

println(msg)

with ctl raise(msg) 42

...

今回のコード例では順序を入れ替えても挙動は変わらないが、組み合わせるEffectによっては変化するものもある

このように、Effectの組み合わせや、handlingの順序の変更などがかなり簡易にできる

具体例をいくつか

継続

listモナド？

たぶん違う

というか非決定を表すndetがあるのでそれを用いた例を書いたほうがおもろそう

以下は、resumeを2回呼んでる例として良さそう

code:koka

effect ctl choice(): bool

fun xor(): choice bool

val p = choice() // ①

val q = choice() // ②

if p then !q else q

fun choice-all(action: () -> <choice|e> a): e list<a>

with handler

ctl choice() resume(False) ++ resume(True)

action()

// xor.choice-all()

実行順番

①でhandleされて、1つめのreusmeにより①にFalseが入る

②で再びhandlerされて、1つめのreusmeにより②にFalseが入る

2つめのreusmeにより②にTrueが入る

①でhandleされて、2つめのreusmeにより①にFalseが入る

②で再びhandlerされて、1つめのreusmeにより②にFalseが入る

2つめのreusmeにより②にTrueが入る

つまり

安直に考えると以下で良さそうだが

code:koka(js)

ctl choice()

resume(False) // A

resume(True)

これだと、Aで再開されてそのまま終わってreturnに行ってしまう

ってことかな